/*
index指向原始数组中的元素
tmp临时数组
k表示临时数组的大小，k初始时为1，然后逐渐扩大到s.size()
当tmp中元素等于k时，说明要将临时数组中元素扔进res中，然后回溯,
去掉tmp尾部元素，放入s[index++]
*/
class Solution {
public:
    vector<int>tmp;
    vector<vector<int>>res;
    void dfs(int k,int index,vector<int>&s)
    {
        if(k==tmp.size())
        {
            res.push_back(tmp);
            return;
        }
        for(int i=index;i<s.size();i++)
        {
            tmp.push_back(s[i]);
            dfs(k,i+1,s);
            tmp.pop_back(); //回溯
           }
    }
    vector<vector<int> > subsets(vector<int> &s) {
        res.push_back(tmp); //把空集扔进去
        for(int i=1;i<=s.size();i++)// k初始时为1，然后逐渐扩大到s.size()
        {
            dfs(i,0,s);
        }
        return res;
    }
};